package 相同的树;

import java.util.LinkedList;
import java.util.Queue;

public class Solution2 {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 使用迭代法，思路和递归一致，只是使用了队列将需要比较的节点放在相邻位置
        Queue<TreeNode> queue = new LinkedList<>(); // 使用LinkedList是因为它可以存放null值
        queue.offer(p);
        queue.offer(q);
        while(!queue.isEmpty()){
            // 取出需要比较的根节点
            p = queue.poll();
            q = queue.poll();
            if(p==null&&q==null)
                continue;
            // 如果出现下面的情况，则直接返回false
            // 情况一：一个根节点为null，一个不为null
            // 情况二：两个根节点的值不相等
            if(p==null||q==null||p.val!=q.val)
                return false;
            // 左树的左孩子和右树的左孩子
            queue.offer(p.left);
            queue.offer(q.left);
            // 左树的右孩子和右树的右孩子
            queue.offer(p.right);
            queue.offer(q.right);
        }
        return true;
    }
}
